package d5;

/**
 * [
 * [1,   4,  7, 11, 15],
 * [2,   5,  8, 12, 19],
 * [3,   6,  9, 16, 22],
 * [10, 13, 14, 17, 24],
 * [18, 21, 23, 26, 30]
 * ]
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
 */
public class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        //若二位数组是一维数组呢
        int m = matrix.length;
        int n = matrix[0].length;
        int i = m - 1; // 横坐标
        int j = 0; // 纵坐标
        // 从二维数组的左下角开始遍历
        while (true) {
            if (i == -1) {
                return false;
            }
            if (j == n) {
                return false;
            }
            int value = matrix[i][j];
            if (target == value) {
                return true;
            }

            if (target > value) {
                j += 1;
            } else {
                i -= 1;
            }
        }
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
        boolean number = new Solution().findNumberIn2DArray(matrix, 12);
        System.out.println(number);
    }
}
